赢的场数都确定了，$p$ 一点用都没有，我们要算出得分之和以后除以 $C(n + m, n)$。所以这是道计数题？
不能小于 $0$，想到了啥，卡特兰数！考虑平面上向右向上走问题
假设 $n \geq m$, 从 $(0, 0)$ 走到 $(n, m)$ 贡献是 $n - m$，方案数是 $C(n + m, n) - C(n + m, n + 1)$，就是用总数 - 碰到了边界线的方案数
从 $(0, 0)$ 走到 $(n, m - 1)$ 贡献是 $n - m + 1$，方案数是 $C(n + m, n + 1) - C(n + m, n + 2)$
…
所以总贡献是 $\sum \limits_{i = 0}^{m} (C(n + m, n + i) - C(n + m, n + i + 1))(n - m + i) = (n - m)C(n + m, n) + \sum\limits_{i = 0}^{m - 1}C(n + m, i)$
$n < m$ 会怎么样，$\sum \limits_{i = m - n}^{m} (C(n + m, n + i) - C(n + m, n + i + 1))(n - m + i) = \sum\limits_{i = 0}^{n - 1}C(n + m, i)$
这样就结束啦（
哦不 多组询问。。
发现形如 $f(n, k) = \sum\limits_{i = 0}^k C(n, i)$ 的东西很难求
发现 $f(n, k) = \sum\limits_{i = 0}^k C(n - 1, i - 1) + C(n - 1, i) = 2f(n - 1, k) - C(n - 1, k)$
发现知道了 $f(n, k)$ 就可以在 $O(1)$ 时间内推出 $f(n \pm 1, k)$ 和 $f(n, k \pm 1)$！
莫队求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, N = 5e5 + 10;
ll T, p, unit = 500, tot;
ll ans[N], fac[N], inv[N], divv[N];
struct que { ll n, k, id; }q[N];
ll quick_pow(ll a, ll b) {
ll ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
} return ret;
}
void pre(int n) {
fac[0] = inv[0] = inv[1] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
rep(i, 2, n) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
rep(i, 2, n) inv[i] = inv[i] * inv[i - 1] % mod;
}
ll C(ll n, ll m) {
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
bool cmp(que a, que b) {
return a.n / unit == b.n / unit ? a.k < b.k : a.n / unit < b.n / unit;
}
int main() {
cin >> T >> p;
pre(500000);
rep(i, 1, T) {
ll n, m;
scanf("%lld%lld", &n, &m);
if (n >= m) {
ans[i] = (n - m) * C(n + m, n) % mod;
q[i].k = m - 1;
} else {
q[i].k = n - 1;
}
q[i].id = i;
q[i].n = n + m;
divv[i] = fac[n] * fac[m] % mod * inv[n + m] % mod;
}
sort(q + 1, q + T + 1, cmp);
q[0].n = -1e9;
ll nn = 0, kk = 0;
rep(i, 1, T) {
if (q[i].k < 0) continue;
if (q[i - 1].k < 0 || q[i - 1].n / unit < q[i].n / unit) {
nn = q[i].n, kk = q[i].k;
tot = 0;
rep(j, 0, kk) (tot += C(nn, j)) %= mod;
} else {
while (nn < q[i].n) tot = (tot * 2 % mod - C(nn, kk) + mod) % mod, ++nn;
while (nn > q[i].n) --nn, tot = (tot + C(nn, kk)) % mod * inv[2] % mod;
while (kk < q[i].k) ++kk, (tot += C(nn, kk)) %= mod;
}
(ans[q[i].id] += tot + mod) %= mod;
}
rep(i, 1, T) printf("%lld\n", ans[i] * divv[i] % mod);
return 0;
}
|